
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
                               proc.c
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
                                                    Forrest Yu, 2005
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

#include "type.h"
#include "const.h"
#include "protect.h"
#include "string.h"
#include "proc.h"
#include "global.h"
#include "proto.h"
#include "cfsrbt.h"
#include "delaylist.h"

/*======================================================================*
                              schedule
 *======================================================================*/

extern int cfs_ticks;

//默认调度周期 48
unsigned int sysctl_sched_latency = 48;
//默认调度最小粒度 4
unsigned int sysctl_sched_min_granularity = 4;
// 默认一个调度周期内的进程数：sysctl_sched_latency / sysctl_sched_min_granularity
static unsigned int sched_nr_latency = 12;

// 初始化红黑树根节点
struct rb_root cfs_tree_root = RB_ROOT;

cfs_node cfs_list[NR_PCBS + 1];
bool in_cfs[NR_PCBS + 1] = {0};
cfs_node* cur_proc, *next_proc;
int cfs_cnt = 0;

// 延迟队列 
delaylist dlist;
delay_t delay_nodes[NR_PCBS + 1];

// 初始化延迟队列 
void init_delay() 
{
	init_delaylist(&dlist, NR_PCBS);
	for (int i = 0; i < NR_PCBS; ++i) init_delay_node(&delay_nodes[i], &proc_table[i]);
}

// 初始化cfs树
void init_cfs()
{
	// uart_kprintf("init cfs tree\n");
	gsch = CFS;
	PROCESS* p;
	int i = 0;
	cfs_cnt = 0;
	for (p = proc_table, i = 0; p < proc_table+NR_PCBS; p++, i++)		
	{
		in_cfs[i] = false;
		cfs_remove_process(&cfs_tree_root, p);
		cfs_node_init(&cfs_list[i], p, 0);
		if (p->task.stat == READY) {
			// uart_kprintf("init cfs insert pid:%d\n", p->task.pid);
			cfs_insert(&cfs_tree_root, &cfs_list[i]);
			set_nice(&cfs_list[i], -5);
			cfs_cnt++;
			in_cfs[i] = true;
		}
	}
	// cur_proc = &cfs_list[p_proc_current->task.pid];
	// print_cfs_scheduler(&cfs_tree_root);
	// sleep(2000000);
	// print_cfs_scheduler(&cfs_tree_root);

} 

void tmp_print_cfs() 
{
	print_cfs_scheduler(&cfs_tree_root);
}

// 刷新cfs树
void flush_cfs()
{
	PROCESS* p;
	int i = 0;
	for (p = proc_table, i = 0; p < proc_table+NR_PCBS; p++, i++)		
	{
		if (p->task.stat == READY && in_cfs[i] == false) {
			cfs_node_init(&cfs_list[i], p, 0);
			// 为了避免老程序饥饿的情况以及保证新进程能被优先调度，将新进程以cfstree中最小vruntime - 1插入
			// runtime_t new_vruntime = get_min_vruntime(&cfs_tree_root) - 1;
			// set_vruntime(&cfs_list[i], new_vruntime >= 0 ? new_vruntime : 0);
			cfs_insert(&cfs_tree_root, &cfs_list[i]);
			cfs_cnt++;
			in_cfs[i] = true;
		}
		else if (p->task.stat != READY && in_cfs[i] == true){
			cfs_remove_process(&cfs_tree_root, p);
			cfs_cnt--;
			in_cfs[i] = false;
		}
	}
	// cur_proc = &cfs_list[p_proc_current->task.pid];
	// if (ticks % 52 == 0)
	print_cfs_scheduler(&cfs_tree_root);
}

void order_schedule();
void cfs_schedule();

void schedule()
{
	if (gsch == CFS)
		cfs_schedule();
	else if (gsch == ORDER)
		order_schedule();
	// order_schedule();

	// if (ticks > 500) cfs_schedule();
	// else order_schedule();
}

void order_schedule()
{
	PROCESS* p;
	int	 greatest_ticks = 0;
	// static int test = 0;
	// if (!test) sys_malloc(1);
	// test++;
	// Added by xw, 18/4/21
	if (p_proc_current->task.stat == READY && p_proc_current->task.ticks > 0) {		
		p_proc_next = p_proc_current;	//added by xw, 18/4/26
		// uart_kprintf("tick: %d; next_proc is %d\n", ticks, p_proc_next->task.pid);
		return;
	}

	while (!greatest_ticks) 
	{
		for (p = proc_table; p < proc_table+NR_K_PCBS; p++)		//edit by visual 2016.4.5
		{
			if (p->task.stat == READY && p->task.ticks > greatest_ticks)  //edit by visual 2016.4.5
			{
				greatest_ticks = p->task.ticks;
				// p_proc_current = p;
				p_proc_next	= p;	//modified by xw, 18/4/26
				// uart_kprintf("tick: %d; next_proc is %d\n", ticks, p_proc_next->task.pid);

			}

		}

		if (!greatest_ticks) 
		{
			for (p = proc_table; p < proc_table+NR_K_PCBS; p++) //edit by visual 2016.4.5
			{
				p->task.ticks = DEFAULT_TICKS;
			}
		}
	}
}

void cfs_schedule()
{
	// disable_int();
	PROCESS* p;
	cur_proc = &cfs_list[p_proc_current->task.pid];
	assert(cur_proc->proc->task.pid <= 12);
	assert(cur_proc->vruntime >= 0);
	if (cur_proc->start == 0) cur_proc->start = ticks;

	int myticks = ticks - cur_proc->start; // 计算已运行的时间

	// 当程序运行准备好或者没有运行满最短时长，直接返回
	if (p_proc_current->task.stat == READY && myticks < sysctl_sched_min_granularity) {	
		p_proc_next = p_proc_current;	
		// enable_int();
		return;
	}

	// uart_kprintf("cfs_ticks is %d\n", cfs_ticks);
	// if (p_proc_current->task.stat != READY) {
	// 	cfs_remove_process(&cfs_tree_root, p_proc_current);
	// 	in_cfs[p_proc_current->task.pid] = false;
	// }
	
	// 更新虚拟时长，并将更新其在cfs树上的位置
	update_vruntime(cur_proc, myticks);
	// add_vruntime(cur_proc, myticks);
	cfs_update_vruntime(&cfs_tree_root, cur_proc, cur_proc->vruntime);
	// cfs_remove(&cfs_tree_root, cur_proc);
	// cfs_insert(&cfs_tree_root, cur_proc);
	assert(cur_proc->proc->task.pid <= 12);
	assert(cur_proc->vruntime >= 0);


	// 刷新cfs树
	// uart_kprintf("cur_proc->pid is %d, start = %d\n", cur_proc->proc->task.pid, cur_proc->start);

	flush_cfs();

	while (1) {
		p_proc_next = cfs_schedule_next(&cfs_tree_root);
		// uart_kprintf("ticks is %d\n", ticks);
		// uart_kprintf("next_proc is %d\n", p_proc_next->task.pid);
		// uart_kprintf("cfs_ticks is %d\n", cfs_ticks);
		// uart_kprintf("myticks is %d\n", myticks);
		if (p_proc_next->task.stat == READY) {
			next_proc = &cfs_list[p_proc_next->task.pid];
			next_proc->start = ticks;
			// cfs_ticks = 0;
			// kprintf("cur_proc is %d\n", p_proc_next->task.pid);
			// uart_kprintf("cur_proc is\n");
			// enable_int();
			return;
		}
		else {
			// uart_kprintf("remove_proc is %d, cfs_cnt = %d\n", p_proc_next->task.pid, cfs_cnt);
			// uart_kprintf("cur_proc->pid is %d\n", cur_proc->proc->task.pid);

			in_cfs[p_proc_next->task.pid] = false;
			cfs_remove_process(&cfs_tree_root, p_proc_next);
			cfs_cnt--;
			if (cfs_cnt <= 0) {
				init_cfs();
			} 
		}

	}
}

/*======================================================================*
                           alloc_PCB  add by visual 2016.4.8
 *======================================================================*/
 PROCESS* alloc_PCB()
{//分配PCB表
	 PROCESS* p;
	 int i;
	 p=proc_table+NR_K_PCBS;//跳过前NR_K_PCBS个
	 for(i=NR_K_PCBS;i<NR_PCBS;i++)
	 {
	   if(p->task.stat==IDLE)break;
	   p++;	
	 }
	if(i>=NR_PCBS)	return 0;   //NULL
	else	return p;
}

/*======================================================================*
                           free_PCB  add by visual 2016.4.8
 *======================================================================*/
 void free_PCB(PROCESS *p)
{//释放PCB表
	p->task.stat=IDLE;
}

/*======================================================================*
                           yield and sleep
 *======================================================================*/
//used for processes to give up the CPU
void sys_yield()
{
	p_proc_current->task.ticks = 0;	/* modified by xw, 18/4/27 */
	sched();	//Modified by xw, 18/4/19
}

//used for processes to sleep for n ticks
void sys_sleep(int n)
{
	p_proc_current->task.delay = n;
	insert_delay_node(&dlist, &delay_nodes[p_proc_current->task.pid]);
	// print_delay_list(&dlist);

	p_proc_current->task.stat = SLEEPING;
	sched();
}


// void sys_sleep(int n)
// {
// 	int ticks0;
	
// 	ticks0 = ticks;
// 	p_proc_current->task.channel = &ticks;
	
// 	while(ticks - ticks0 < n){
// 		p_proc_current->task.stat = SLEEPING;
// //		save_context();
// 		sched();	//Modified by xw, 18/4/19
// 	}
// }

/*invoked by clock-interrupt handler to wakeup 
 *processes sleeping on ticks.
 */
void sys_wakeup(void *channel)
{
	minus_delay(&dlist);
	// print_delay_list(&dlist);
	delay_t* dnode = dlist.head;
	if (!dnode) return;
	PROCESS *p = dnode->proc;

	while (dnode && p->task.stat == SLEEPING && dnode->delay == 0) {
		remove_delay_node(&dlist, &delay_nodes[p->task.pid]);
		p->task.stat = READY;
		p->task.delay = 0;
		dnode = dlist.head;
		if (!dnode) return;
		p = dnode->proc;
	}
}

// void sys_wakeup(void *channel)
// {
// 	PROCESS *p;
	
// 	for(p = proc_table; p < proc_table + NR_PCBS; p++){
// 		if(p->task.stat == SLEEPING && p->task.channel == channel){
// 			p->task.stat = READY;
// 		}
// 	}
// }

//added by zcr
int ldt_seg_linear(PROCESS *p, int idx)
{
	struct s_descriptor * d = &p->task.ldts[idx];
	return d->base_high << 24 | d->base_mid << 16 | d->base_low;
}

void* va2la(int pid, void* va)
{
	if(kernel_initial == 1){
		return va;
	}
	
	PROCESS* p = &proc_table[pid];
	u32 seg_base = ldt_seg_linear(p, INDEX_LDT_RW);
	u32 la = seg_base + (u32)va;
	
	return (void*)la;
}
//~zcr

// 系统调用nice
int do_nice(u32 pid, int incr) {
	if (incr < -20 || incr > 19) return -1;
    struct cfs_node* node = cfs_search_pid(&cfs_tree_root, pid);
	// uart_kprintf("pid: %d; nice: %d; incr: %d\n", node->proc->task.pid, node->nice, incr);
	if (!node) return -1;

	if (incr) set_nice(node, node->nice + incr);
	// uart_kprintf("pid: %d; nice: %d;\n", node->proc->task.pid, node->nice);

	
	return node->nice;
}